package leetcode_801_900;

import java.util.ArrayList;
import java.util.List;

public class LeeCode_842 {
    public static void main(String[] args) {
//        System.out.println(splitIntoFibonacci("1101111"));
//        System.out.println(splitIntoFibonacci("112358130"));
//        System.out.println(splitIntoFibonacci("0123"));
        System.out.println(splitIntoFibonacci("01123581321345589"));
    }
    private static List<Integer> splitIntoFibonacci(String num) {
        List<Integer> ans = new ArrayList<>();
        boolean[] flag = new boolean[1];
        dfs(new ArrayList<>(), num, 0, ans, flag);
        return ans;
    }
    private static void dfs(List<Integer> list, String s, int index, List<Integer> ans, boolean[] flag){
        int n = s.length();
        if (index == n) {
            flag[0] = true;
            ans.addAll(list);
            return;
        }
        if (index > n)
            return;
        if (list.size() < 2){
            for (int i = index + 1; i < n && i - index < 11; i++) {
                if (s.charAt(index) == '0'){
                    ArrayList<Integer> newL = new ArrayList<>(list);
                    newL.add(0);
                    dfs(newL, s, i, ans, flag);
                }else {
                    long num = Long.parseLong(s.substring(index, i));
                    if (num < Integer.MAX_VALUE) {
                        ArrayList<Integer> newL = new ArrayList<>(list);
                        newL.add((int) num);
                        if (flag[0])
                            return;
                        dfs(newL, s, i, ans, flag);
                    }
                }
            }
        }else {
            long sum = list.get(list.size() - 1) + list.get(list.size() - 2);
            String next = Long.toString(sum);
            if (index + next.length() <= s.length() && s.startsWith(next, index)){
                list.add((int) sum);
                if (flag[0])
                    return;
                dfs(list, s, index + next.length(), ans, flag);
            }
        }
    }
}
